The calculation of the distance between two points is a common operation performed today. One application of this basic distance measure is in recognition routines and algorithms where a distance measure is used to quantify the difference between an unknown and a reference pattern, such that a determination can be made as to the identity of the unknown.
One widely known distance measure is the Euclidean distance measure. The Euclidean distance measure is the straight line distance between two points and is illustrated in conjunction with FIG. 1A. Referring to FIG. 1A, a plot of two points A and B is shown on an X-Y axis. Point A has coordinates of (x.sub.a, y.sub.a) and point B has coordinate of (x.sub.b, Y.sub.b). The Euclidean distance (Ed) between point A and point B is determined according to the equation: ##EQU1##
Another distance measure is referred to as the Manhattan distance measure, or the "city block distance." The Manhattan distance is the distance between two points as measured by a path comprised of horizontal and vertical perpendicular paths and is illustrated in conjunction with FIG. 1B. Referring to FIG. 1B, a grid plot is shown having perpendicular horizontal and vertical lines. Point A is shown on the grid plot with coordinates (x.sub.a, y.sub.a), and point B is shown on the grid plot with coordinates (x.sub.b, Y.sub.b). The Manhattan distance (Md) between point A and point B is determined according to the equation: EQU Md=.vertline.x.sub.a -x.sub.b .vertline.+.vertline.y.sub.a -y.sub.b .vertline.
Today, in various fields and applications that require that these distance measures be calculated very quickly and for large numbers of points, computers are often employed. In order to calculate the Manhattan distance, these computers must determine the absolute value of a difference. In other words, a set of instructions must be used which can calculate the absolute value of a difference.
Where the instruction set includes an absolute value instruction, the calculation of the absolute value of the difference required a first instruction to calculate the difference between the two numbers (e.g., operands) and then a second instruction to produce the absolute value of that quantity. An example of such a set of instruction for determining the absolute value of the difference, x, is shown below: EQU temp=a-b EQU x=abs (temp)
When the instruction set does not include an absolute value instruction, the calculation of the absolute value of the difference includes a first instruction to calculate the difference. The difference result that is produced is compared with zero. A branch instruction is then required which branches if the difference is positive. If the result is not positive, the negative of the result is taken. Upon taking the branch, the program jumps to the instruction code which immediately follows the negative instruction. An example of such a set of instructions is shown below:
______________________________________ temp = a - b cmp zero branch positive .fwdarw. nxt temp nxt: remainder of code ______________________________________
It is desirable to have one instruction for generating the absolute value of a difference.
Note that the two examples of instruction code given above also suffer from the time required to produce their results. That is, each of the cases illustrated above require numerous machine, or clock, cycles to complete performance, particularly in the case when the programming language does not have an absolute value instruction. In that case, the use of compare and branch instructions requires a large number of cycles for their completion. It is desirable to have an instruction which generates the absolute value of a difference in one clock cycle.
The present invention provides a method and apparatus for generating the absolute value of a difference. The present invention generates the absolute value of a difference in one clock cycle. By generating the absolute value of a difference in less clock cycles than the prior art, the application utilizing the calculation is able to perform its designated function more quickly.